문제 설명

어떤 수를 서로 다른 소수 3개의 합으로 표현하는 경우의 수를 구하려 합니다. 예를 들어 33은 총 4가지 방법으로 표현할 수 있습니다.

  • 3+7+23
  • 3+11+19
  • 3+13+17
  • 5+11+17

자연수 n이 매개변수로 주어질 때, n을 서로 다른 소수 3개의 합으로 표현하는 경우의 수를 return 하는 solution 함수를 작성해주세요.

제한 조건

  • n은 1,000 이하인 자연수입니다.

입출력 예

n return
33 4
9 0
입출력 예 설명

예시 #1 문제에 나온 예와 같습니다.

예시 #2 9는 서로 다른 세 소수의 합으로 나타낼 수 없습니다.

나의풀이

첫번째 풀이

소스

def get_prime_list(n):
    num_list = [True] * n

    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if num_list[i]:
            for j in range(i+i, n, i):
                num_list[j] = False

    return [i for i in range(2, n) if num_list[i]]


def solution(n):
    answer = 0

    prime_list = get_prime_list(n)
    prime_num = len(prime_list)
    for i in range(prime_num-2):
        for j in range(i+1, prime_num-1):
            for k in range(j+1, prime_num):
                if prime_list[i] + prime_list[j] + prime_list[k] == n:
                    answer += 1

    return answer

설명

  • 소수를 구하는 공식인, 에라토스테네스의 체를 사용.
  • 주어진 n에 대하여 소수 리스트를 구한다.
  • 해당 리스트에서 나올 수 있는 경우의 수를 모두 구한 후 결과값이 n과 같으면 정답 1씩 더해주는 방식.
  • 에라토스테네스의 체는 외워두자.
  • 조합을 직접 구하였는데 itertools의 combinations를 사용하자.

결과

통과

리뷰

  • 오퍼레이터 사이는 띄워쓰는 것이 좋습니다. (m = int(n ** 0.5))

  • 조합을 combinations 함수를 통해 쉽게 구할 수 있습니다. :)

    from itertools import combinations
...
answer = [sum(i) for i in list(combinations(prime_list, 3))].count(n)